package com.ai.zuochengyun.phase01.class01;

import java.util.Arrays;

/**
 * 基数排序
 */
public class Code18_RadixSort {

    public static void radixSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        process(arr, 0, arr.length - 1, maxbits(arr));
    }

    private static void process(int[] arr, int left, int right, int digit) {
        int radix = 10;
        int i = 0, j = 0;
        int size = right - left + 1;
        int[] help = new int[size];
        // 有多少位，就进出多少次
        for (int d = 1; d <= digit; d++) {
            // 创建10个空间，代替10个桶
            // count[0]表示当前位（d位）小于等于0的数字有多少个
            // count[1]表示当前位（d位）小于等于1的数字有多少个
            // count[2]表示当前位（d位）小于等于2的数字有多少个
            // ......
            // count[i]表示当前位（d位）小于等于i的数字有多少个
            int[] count = new int[radix];
            for (i = left; i <= right; i++) {
                j = getDigit(arr[i], d);
                // 词频累加
                count[j]++;
            }

            // 统计小于等于当前当前位上的数字的个数
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }

            // 从右往左倒数字
            for (i = right; i >= left; i--) {
                j = getDigit(arr[i], d);
                // 当前位有count[j]这么多个数组，那么对应存储的下标就是0~count[j]- 1]
                // 将arr[i]的数从右往左放到0~count[j]- 1]下标中
                help[count[j] - 1] = arr[i];
                // 放了一个数后，还剩余的数量就减少一个
                count[j]--;
            }

            // 将排序好的数写入原始的桶
            for (i = left, j = 0; i <= right; i++, j++) {
                arr[i] = help[j];
            }
        }
    }

    /**
     * 提取每个数对应位上的数字，比如提取54 的个位4，的百位5
     *
     * @param num
     * @param d
     * @return
     */
    private static int getDigit(int num, int d) {
        // 先获取商，然后再求余数
        return (num / ((int) Math.pow(10, d - 1))) % 10;
    }

    private static int maxbits(int[] arr) {
        // 找到最大的数
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            max = Math.max(max, num);
        }

        // 获取最大的数是多少位
        int res = 0;
        while (max != 0) {
            res++;
            // 求余数
            max = max / 10;
        }
        return res;
    }

    public static void test(int[] arr) {
        Arrays.sort(arr);
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) (Math.random() * (maxSize + 1))];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random() * (maxValue+1));
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        int[] res = new int[arr.length];
        System.arraycopy(arr, 0, res, 0, arr.length);
        return res;
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");
        }
    }

    public static boolean isEquals(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int testTimes = 500000;
        int maxSize = 100;
        int maxValue = 100000;
        boolean suc = true;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);

            test(arr1);
            radixSort(arr2);

            if (!isEquals(arr1, arr2)) {
                suc = false;
                System.out.println("oops");
                printArray(arr1);
                System.out.println();
                printArray(arr2);
                break;
            }
        }
        System.out.println("排序结束");
    }
}
